package com.cuz.daileetcode.暴力递归记忆化搜索动态规划;

/**
 * 见 【暴力递归-记忆化搜索-动态规划4】
 */
public class NumberWaysToChangeMoney {

    public static void main(String[] args) {
        int[] arr = {2, 5, 20, 1};
        int aim = 100;
        System.out.println(Recursion.numberWaysToChangeMoney(arr, aim));
        System.out.println(DynamicProgramming.numberWaysToChangeMoney1(arr, aim));
        System.out.println(DynamicProgramming.numberWaysToChangeMoney2(arr, aim));
    }

    static class Recursion {
        static int numberWaysToChangeMoney(int[] arr, int aim) {
            if (aim < 0 || arr == null || arr.length == 0) {
                return 0;
            }
            //使用arr中的钱，可以使用从0位置开始的钱，剩余需要凑的钱 aim
            return recursion(arr, 0, aim);
        }

        private static int recursion(int[] arr, int index, int rest) {
            int waysToChange = 0;
            //如果已经使用完所以的钱，（使用0张也是使用）
            if (index == arr.length) {
                //剩余需要凑的是0元 那么返回1
                if (rest == 0) {
                    waysToChange = 1;
                } else {
                    //剩余的钱步数不是0 但钱都使用了个边 那么说明这个方法不行
                    //比如100，200，300，让凑4，无论如何都凑不出
                    //或者 2，5，10，100，凑90，2，5，10使用完并没有凑处90剩余钱为10，
                    // 接下来100不可能凑出来10，选择0张100 index到达数组末尾，但rest=10
                    //返回0
                    waysToChange = 0;
                }
            } else {
                //sheet 当前选择多少张 arr[index]表示的钱
                //循环退出的条件sheets * arr[index] < rest 选择的张*当前的面值<剩余钱
                //比如当前面值 5，剩余需要凑的钱为200，最多选到40，如果选择41 那么接下来没有尝试的必要了
                for (int sheets = 0; sheets * arr[index] <= rest; sheets++) {
                    //如果sheet =0 arr=[5,10,25,1]，凑100
                    //sheet=0 就是选择0张5元 index+1 选择index+1后的钱 也就是10，25，1 ，需要凑的的钱就是100
                    //sheet=1 就是选择01张5元 index+1 选择index+1后的钱 也就是10，25，1 ，需要凑的的钱就是100-5
                    //sheet=20 就是选择01张5元 index+1 选择index+1后的钱 也就是10，25，1 ，需要凑的的钱就是0
                    //index=2还会进循环 但是sheet只能等于0  让 25和1凑0
                    //index=3 还会进循环 但是sheet只能等于0，让1 凑0
                    //index=4 这个时候进入上的if rest=0 返回1 ，方法数+1
                    waysToChange += recursion(arr, index + 1, rest - arr[index] * sheets);
                }
            }
            return waysToChange;
        }
    }

    static class DynamicProgramming {
        static int numberWaysToChangeMoney1(int[] arr, int aim) {
            if (aim < 0 || arr == null || arr.length == 0) {
                return 0;
            }
            //dp数组
            int[][] dp = new int[arr.length + 1][aim + 1];
            //初始化dp数组 只有最后一行 的第一列为1 其他为0 java 默认为0
            dp[arr.length][0] = 1;
            //从下到上 最后一行已经填好了 从到第二行填
            for (int index = arr.length - 1; index >= 0; index--) {
                for (int rest = 0; rest <= aim; rest++) {
                    //当前位置的值 dp[index][rest]=下一行 dp[index + 1][rest - arr[index] * sheets]的值累加
                    int waysToChange = 0;
                    for (int sheets = 0; sheets * arr[index] <= rest; sheets++) {
                        waysToChange += dp[index + 1][rest - arr[index] * sheets];
                    }
                    dp[index][rest] = waysToChange;
                }
            }
            return dp[0][aim];
        }

        static int numberWaysToChangeMoney2(int[] arr, int aim) {
            if (aim < 0 || arr == null || arr.length == 0) {
                return 0;
            }
            //dp数组
            int[][] dp = new int[arr.length + 1][aim + 1];
            //初始化dp数组 只有最后一行 的第一列为1 其他为0 java 默认为0
            dp[arr.length][0] = 1;
            //从下到上 最后一行已经填好了 从到第二行填
            for (int index = arr.length - 1; index >= 0; index--) {
                for (int rest = 0; rest <= aim; rest++) {
                    int waysToChange = dp[index + 1][rest];
                    if (rest - arr[index] >= 0) {
                        waysToChange += dp[index][rest - arr[index]];
                    }
                    dp[index][rest] = waysToChange;
                }
            }
            return dp[0][aim];
        }
    }
}
